package org.labuladong.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-1:34
 * @Description: 76. 最小覆盖子串
 *
 * 给你⼀个字符串 s 、⼀个字符串 t，返回 s 中涵盖 t 所有字符的最⼩⼦串；
 * 如果 s 中不存在涵盖 t 所有字符的⼦串，则返回空字符串 ""。
 *
 * 1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
 *
 * 2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
 *
 * 3、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
 *
 *
 * 如果一个字符进入窗口，应该增加 window 计数器；
 * 如果一个字符将移出窗口的时候，应该减少 window 计数器；
 * 当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
 *
 * @version: 1.0
 */

class Solution2 {
	public String minWindow(String s, String t) {
		/**
		 * 首先，初始化 window 和 need 两个哈希表，
		 * 记录窗口中的字符和需要凑齐的字符：
		 */
		// 记录所需的字符出现次数
		Map<Character, Integer> need = new HashMap<>();
		// 记录 window 中的字符出现次数
		Map<Character, Integer> window = new HashMap<>();
		for (char c : t.toCharArray()) {
			need.put(c, need.getOrDefault(c, 0) + 1);
		}

		// 使用 left 和 right 变量初始化窗口的两端
		int left = 0, right = 0;
		// 其中 valid 变量表示窗口中满足 need 条件的字符个数
		int valid = 0;
		// 记录最小覆盖子串的起始索引及长度
		int start = 0, len = Integer.MAX_VALUE;
		while (right < s.length()) {
			// c 是将移入窗口的字符
			char c = s.charAt(right);
			// 扩大窗口
			right++;
			// 进行窗口内数据的一系列更新
			if (need.containsKey(c)) {
				window.put(c, window.getOrDefault(c, 0) + 1);
				if (window.get(c).equals(need.get(c)))
					valid++;
			}

			// 判断左侧窗口是否要收缩
			while (valid == need.size()) {
				// 在这里更新最小覆盖子串
				if (right - left < len) {
					start = left;
					len = right - left;
				}
				// d 是将移出窗口的字符
				char d = s.charAt(left);
				// 缩小窗口
				left++;
				// 进行窗口内数据的一系列更新
				if (need.containsKey(d)) {
					if (window.get(d).equals(need.get(d)))
						valid--;
					window.put(d, window.get(d) - 1);
				}
			}
		}
		// 返回最小覆盖子串
		return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
	}
}